package 字符串;

import java.util.ArrayList;
import java.util.List;

/**
 * 68. 文本左右对齐
 * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 * 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 *
 * 这道题确实要使用贪心思想，通过每一步的累加得到最优解，然后得到结果。
 * 方法思路：
 *  1：分割单词成多行：
 *      使用一个临时列表来存储当前行单词，累加单词长度，如果加上下一个单词会超过最大宽度，则结束当前行，开始新一行；
 *  2：处理每一行的对齐：
 *      如果是最后一行，单词之间用单个空格连接，然后在后面补充空格达到最大宽度；
 *      如果不是最后一行：
 *          如果只有一个单词，则左对齐，后面补充空格；
 *          如果有多个单词，计算总空格数，并均匀分配空格，并且是前面的间隔优先分配额外的空格；
 */
public class L_68 {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        List<String> currentLine = new ArrayList<>();
        int currentLength = 0;
        for(String word : words){
            // 如果累加单词的长度大于最大宽度，则结束当前行，开始新一行； -- 满足条件的一个结果
            if(currentLength + word.length() + (currentLine.size() > 0 ? 1 : 0) > maxWidth){
                // 添加结果
                result.add(formatLine(currentLine, maxWidth, false));
                // 重置数组
                currentLine.clear();
                currentLength = 0;
            }
            currentLine.add(word);
            // 每添加一个单词,至少要累加一个空格进行长度统计
            currentLength += word.length() + (currentLine.size() > 1 ? 1 : 0);
        }
        // 如果还有单词每统计完，则是最后一行，那么添加最后一行
        if(currentLine.size() > 0){
            result.add(formatLine(currentLine, maxWidth, true));
        }
        return result;
    }

    /**
     * 格式化每一行
     * 按照思路规则，格式化每一行，即给每一行添加空格达到最大长度。
     * @param words
     * @param maxWidth
     * @param isLastLine 最后一行的表示
     * @return
     */
    private String formatLine(List<String> words,int maxWidth,boolean isLastLine){
        // 如果是最后一行，单词之间用单个空格连接，然后在后面补充空格达到最大宽度；
        if(isLastLine){
            String line = String.join(" ", words); // 单词之间使用空格拼接
            return line + generateSpace(maxWidth - line.length()); // 在后面补充空格
        }else { // 不是最后一行
            if(words.size() == 1){ // 如果只有一个单词，则左对齐，后面补充空格；
                return words.get(0) + generateSpace(maxWidth - words.get(0).length());
            }else { // 如果有多个单词，计算总空格数，并均匀分配空格，前面的间隔优先分配额外的空格；
                int totalLetters = 0; // 单词总长度
                for (String word : words){
                    totalLetters += word.length();
                }
                // 需要补充的空格数
                int totalSpaces = maxWidth - totalLetters;
                // 每个单词间隔之前应该填充的平均空格数
                int sapceBetweenWords = totalSpaces / (words.size() -1);
                // 额外的取余空格数
                int extraSpace = totalSpaces % (words.size() -1);
                // 对单词之间进行填充，并且是前面的间隔优先分配额外的空格；
                StringBuilder line = new StringBuilder();
                for (int i = 0; i < words.size(); i++) {
                    line.append(words.get(i));
                    if(i < words.size() -1){
                        line.append(generateSpace(sapceBetweenWords + (extraSpace-- > 0 ? 1 : 0)));
                    }
                }
                return line.toString();
            }
        }
    }

    /**
     * 根据num数生成多少个空格字符
     * @param num
     * @return
     */
    private String generateSpace(int num){
        return new String(new char[num]).replace('\0',' ');
    }
}
